package com.whosly.demo.benchmark.sortalgorithms.insertion;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 二分法插入排序(Dichotomy Insertion Sort)
 *
 * 性能结果表明， >>1 位运算的性能较好
 *
 * @author fengyang
 * @date 2023/6/13 下午2:48
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class DichotomyInsertionSort implements ISortingAlgorithms
{

    /**
     * 除法方式
     */
    public static final int M0 = 0;

    /**
     * 位移方式
     */
    public static final int M1 = 1;

    /**
     * 实现方式
     */
    private int mode;

    public DichotomyInsertionSort()
    {
        this(M0);
    }

    public DichotomyInsertionSort(int mode)
    {
        this.mode = mode;
    }

    @Override
    public int[] sorting(int[] arr)
    {
        return sorting(arr, this.mode);
    }

    private int[] sorting(int[] arr, int mode) {
        for (int i = 0; i < arr.length; i++) {
            // 拿到要插入的值 temp。 tmp用于存放临时变量
            int temp = arr[i];

            // left 表示的下标为i的前面有序数组的起点下标，right 表示的是下标为i之前的有序数组的起点终点
            // mid表示子数组中的中间下标
            int left = 0;
            int right = i-1;
            int mid = 0;

            // 循环直到 left>right，此时 left则为要插入的位置。 不满足条件跳出
            while(left <= right){
                // 如果至少含有一个元素的时候就继续循环，进行比较，获得tmp要插入的位置
                if(mode == M0){
                    mid = (left+right)/2;
                }else{
                    mid = (left+right)>>1;
                }

                if(temp < arr[mid]){
                    // 如果 temp 小于中间值，就说明 temp 在左边,所以更改 right 的值
                    //低位
                    right = mid-1;
                }else{
                    // 否则，如果 temp 大于等于中间值，说明 temp 在右边，更改 left 的值
                    //高位
                    left = mid+1;
                }
            }

            // 当 left> right，这时候就意味着没有了元素，这时候可以退出循环了

            // 待插入元素插入到left位置
            if(left != i){
                // 并且 right 的后面都是大于 temp 的元素（也就是说 right + 1这个下标对应的数是最后一个大于 temp 的数),
                // 因此需要将这些元素后移, 对 [left,i-1]之间的元素进行右移一位
                // 这里的for循环之所以是从j = i - 1开始，是因为下标为i前面的有序数组是[0 , i - 1]，
                // 那么我们现在需要将大于等于 temp 的元素往后移，给 temp 插入腾出位置，所以是从i - 1开始遍历，往后移，
                // 直到j = left - 1的时候结束后移
                for (int j = i-1; j >= left; j--) {
                    arr[j+1] = arr[j];
                }

                //把 arr[i]放到正确的位置
                arr[left] = temp;
            }
        }

        return arr;
    }

}
